#include "abb.h"
#include "pila.h"

#include <stdlib.h>
#include <string.h>

enum {ERROR,AGREGADO,REEMPLAZADO,QUITADO};

typedef struct abb_nodo {
							char *clave;
							void *dato;
							size_t altura;
							struct abb_nodo *izquierdo;
							struct abb_nodo *derecho;
						} abb_nodo_t;

struct abb {
			abb_nodo_t *raiz;
			size_t tamanio;
			abb_destruir_dato_t destruir_dato;
			abb_comparar_clave_t comparar_clave;
			};

struct abb_iter {
	pila_t* iter_pila;
};

// Funcion genérica. Intercambia 2 nodos.
void abb_nodo_intercambiar(abb_nodo_t *a, abb_nodo_t *b)
{
	abb_nodo_t aux = *a;
	*a = *b;
	*b = aux;
}
						
abb_nodo_t *abb_nodo_crear(const char *clave, void *dato)
{
	if (!clave)
		return NULL;

	abb_nodo_t *nodo = malloc(sizeof(abb_nodo_t));

	if (!nodo)
		return NULL;

	size_t longitud_clave = strlen(clave)+1;
	nodo->clave = malloc(sizeof(char)*longitud_clave);

	if (!nodo->clave)
		{
			free(nodo);
			return NULL;
		}

	strcpy(nodo->clave,clave);
	nodo->dato = dato;
	nodo->izquierdo = NULL;
	nodo->derecho = NULL;

	nodo->altura = 1;

	return nodo;
}

void abb_nodo_destruir(abb_nodo_t *nodo)
{
	if (!nodo)
		return;

	free(nodo->clave);
	free(nodo);
}

size_t abb_nodo_obtener_altura(const abb_nodo_t *nodo)
{
	if (!nodo)
		return 0;

	return nodo->altura;
}

void abb_nodo_recalcular_altura(abb_nodo_t *nodo)
{
	if (!nodo)
		return;

	size_t altura_izquierdo = abb_nodo_obtener_altura(nodo->izquierdo);
	size_t altura_derecho = abb_nodo_obtener_altura(nodo->derecho);

	nodo->altura = 1 + (altura_derecho > altura_izquierdo?altura_derecho:altura_izquierdo);
}

int abb_nodo_calcular_pendiente(const abb_nodo_t *nodo)
{
	if (!nodo)
		return 0;

	return abb_nodo_obtener_altura(nodo->izquierdo) - abb_nodo_obtener_altura(nodo->derecho);
}

// pendiente < -1
void AVL_rotar_izquierda(abb_nodo_t *nodo)
{
	if (!nodo)
		return;

	abb_nodo_t *nuevo_nodo = nodo->derecho;

	nodo->derecho = nuevo_nodo->izquierdo;

	nuevo_nodo->izquierdo = nuevo_nodo;

	abb_nodo_intercambiar(nodo,nuevo_nodo);

	abb_nodo_recalcular_altura(nuevo_nodo);

	abb_nodo_recalcular_altura(nodo);
}

// pendiente > 1
void AVL_rotar_derecha(abb_nodo_t *nodo)
{
	if (!nodo)
		return;

	abb_nodo_t *nuevo_nodo = nodo->izquierdo;

	nodo->izquierdo = nuevo_nodo->derecho;

	nuevo_nodo->derecho = nuevo_nodo;

	abb_nodo_intercambiar(nodo,nuevo_nodo);

	abb_nodo_recalcular_altura(nuevo_nodo);

	abb_nodo_recalcular_altura(nodo);
}

void CorregirAVL(abb_nodo_t *nodo)
{
	if (!nodo)
		return;

	int pendiente = abb_nodo_calcular_pendiente(nodo);

	if (pendiente > 1)
		AVL_rotar_derecha(nodo);
	else if (pendiente < -1)
		AVL_rotar_izquierda(nodo);
}

abb_nodo_t *abb_nodo_buscar(const abb_nodo_t *nodo, const char *clave, const abb_comparar_clave_t comparar_clave)
{
	if (!nodo || !clave)
		return NULL;

	int cmp = comparar_clave(clave,nodo->clave);

	if (cmp < 0)
	  {
	    if (!nodo->izquierdo)
	      return NULL;
	    return abb_nodo_buscar(nodo->izquierdo,clave,comparar_clave);
	  }
	else if (cmp > 0)
	  {
	    if (!nodo->derecho)
	      return NULL;
	    return abb_nodo_buscar(nodo->derecho,clave,comparar_clave);
	  }

	return (abb_nodo_t *)nodo;
}

void *abb_nodo_obtener(const abb_nodo_t *nodo, const char *clave, abb_comparar_clave_t comparar_clave)
{
	abb_nodo_t *elem = abb_nodo_buscar(nodo,clave,comparar_clave);
	
	if (!elem)
		return NULL;

	return elem->dato;
}

bool abb_nodo_pertenece(const abb_nodo_t *nodo, const char *clave, abb_comparar_clave_t comparar_clave)
{
	return abb_nodo_buscar(nodo,clave,comparar_clave) != NULL;
}

int abb_nodo_agregar(abb_nodo_t *nodo, const char *clave, void *dato, const abb_comparar_clave_t comparar_clave, const abb_destruir_dato_t destruir_dato)
{
	if (!nodo || !clave)
		return ERROR;

	int cmp = comparar_clave(clave,nodo->clave);

	if (!cmp)
		{
			if (destruir_dato && nodo->dato)
				destruir_dato(nodo->dato);
			nodo->dato = dato;
			return REEMPLAZADO;
		}

	int result;

	if (cmp < 0)
		{
			if (nodo->izquierdo)
				result = abb_nodo_agregar(nodo->izquierdo,clave,dato,comparar_clave, destruir_dato);
			else
				result = (nodo->izquierdo = abb_nodo_crear(clave,dato)) != NULL?AGREGADO:ERROR;
		}
	else
		{
			if (!nodo->derecho)
				result = (nodo->derecho = abb_nodo_crear(clave,dato)) != NULL?AGREGADO:ERROR;
			else
				result = abb_nodo_agregar(nodo->derecho,clave,dato,comparar_clave, destruir_dato);
		}

	if (result == AGREGADO)
		{
			abb_nodo_recalcular_altura(nodo);
			CorregirAVL(nodo);
		}

	return result;
}

abb_nodo_t *abb_nodo_buscar_padre(const abb_nodo_t *nodo, const abb_nodo_t *hijo, abb_comparar_clave_t comparar_clave)
{
	if (!nodo || !hijo)
		return NULL;

	if ((nodo == hijo) || (hijo == nodo->derecho) || (hijo == nodo->izquierdo))
		return (abb_nodo_t *)nodo;

	int cmp = comparar_clave(hijo->clave,nodo->clave);

	if ((cmp < 0)/* && nodo->izquierdo*/)
		return abb_nodo_buscar_padre(nodo->izquierdo,hijo,comparar_clave);
	else if ((cmp > 0)/* && nodo->derecho*/)
		return abb_nodo_buscar_padre(nodo->derecho,hijo,comparar_clave);

	return (abb_nodo_t *)nodo;
}

abb_nodo_t *abb_nodo_buscar_sucesor_izquierdo(const abb_nodo_t *nodo)
{
	if (!nodo)
		return NULL;
	
	if (nodo->izquierdo)
		return abb_nodo_buscar_sucesor_izquierdo(nodo->izquierdo);

	return (abb_nodo_t *)nodo;
}

abb_nodo_t *abb_nodo_buscar_sucesor_derecho(const abb_nodo_t *nodo)
{
	if (!nodo)
		return NULL;

	if (nodo->derecho)
		return abb_nodo_buscar_sucesor_derecho(nodo->derecho);

	return (abb_nodo_t *)nodo;
}

bool abb_nodo_tiene_hijos(const abb_nodo_t *nodo)
{
	if (!nodo)
		return false;
	return nodo->derecho || nodo->izquierdo;
}

void *abb_nodo_quitar(abb_nodo_t *nodo, const char *clave, const abb_comparar_clave_t comparar_clave, int *resultado)
{
	if (!nodo || !clave)
		{
			*resultado = ERROR;
			return NULL;
		}

	void *evidencia;
	
	int cmp = comparar_clave(clave,nodo->clave);
	
	if (!cmp)
		{
			*resultado = QUITADO;	// Fue encontrado => es quitado
			evidencia = nodo->dato;
			if (!nodo->derecho && !nodo->izquierdo)
				abb_nodo_destruir(nodo);
			else if (!nodo->derecho)
				{
					abb_nodo_t *heredero = nodo->izquierdo;
					abb_nodo_intercambiar(nodo,heredero);
					abb_nodo_destruir(heredero);
				}
			else if (!nodo->izquierdo)
				{
					abb_nodo_t *heredero = nodo->derecho;
					abb_nodo_intercambiar(nodo,heredero);
					abb_nodo_destruir(heredero);
				}
			else
				{
					abb_nodo_t *sucesor,*temp;

					int pendiente = abb_nodo_calcular_pendiente(nodo);

					if (pendiente > 0)
						{
							sucesor = abb_nodo_buscar_sucesor_derecho(nodo->izquierdo);
							sucesor->derecho = nodo->derecho;
							temp = sucesor;
							while (temp->izquierdo)
								temp = temp->izquierdo;
						}
					else
						{
							sucesor = abb_nodo_buscar_sucesor_izquierdo(nodo->derecho);
							sucesor->izquierdo = nodo->izquierdo;
							temp = sucesor;
							while (temp->derecho)
								temp = temp->derecho;
						}

					abb_nodo_t *padre = abb_nodo_buscar_padre(nodo,sucesor,comparar_clave);

					if (padre->derecho == sucesor)
						padre->derecho = NULL;
					else if (padre->izquierdo == sucesor)
						padre->izquierdo = NULL;

					if (pendiente > 0)
						temp->izquierdo = nodo->izquierdo;
					else
						temp->derecho = nodo->derecho;

					sucesor->altura = nodo->altura;

					abb_nodo_intercambiar(nodo,sucesor);

					abb_nodo_destruir(sucesor);
				}
		}
	else if (cmp < 0)
		{
			abb_nodo_t *temp = nodo->izquierdo;
			bool tiene_hijos = abb_nodo_tiene_hijos(temp);	// Tomamos en cuenta si el nodo a borrar tiene hijos.
			evidencia = abb_nodo_quitar(temp,clave,comparar_clave,resultado);

			if (!tiene_hijos && (*resultado == QUITADO))
				nodo->izquierdo = NULL;

			abb_nodo_recalcular_altura(nodo);
			CorregirAVL(nodo);
		}
	else
		{
			abb_nodo_t *temp = nodo->derecho;
			bool tiene_hijos = abb_nodo_tiene_hijos(temp);
			evidencia = abb_nodo_quitar(temp,clave,comparar_clave,resultado);
			
			if (!tiene_hijos && (*resultado == QUITADO))
				nodo->derecho = NULL;

			abb_nodo_recalcular_altura(nodo);
			CorregirAVL(nodo);
		}

	return evidencia;
}

void abb_nodo_destruir_arbol(abb_nodo_t *nodo, abb_destruir_dato_t destruir_dato)
{
	if (!nodo)
		return;

	abb_nodo_destruir_arbol(nodo->izquierdo,destruir_dato);
	abb_nodo_destruir_arbol(nodo->derecho,destruir_dato);

	if (destruir_dato && nodo->dato)
		destruir_dato(nodo->dato);

	abb_nodo_destruir(nodo);
}

abb_t* abb_crear(abb_comparar_clave_t cmp, abb_destruir_dato_t destruir_dato)
{
	abb_t *abb = malloc(sizeof(abb_t));

	if (!abb)
		return NULL;

	abb->tamanio = 0;
	abb->raiz = NULL;
	abb->destruir_dato = destruir_dato;
	abb->comparar_clave = cmp;
	
	return abb;
}

size_t abb_cantidad(const abb_t *arbol)
{
	if (!arbol)
		return 0;

	return arbol->tamanio;
}

bool abb_esta_vacio(const abb_t *abb)
{
	return !abb->tamanio;
}

bool abb_guardar(abb_t *arbol, const char *clave, void *dato)
{
	if (!arbol || !clave)
		return false;

	int result;

	if (!abb_esta_vacio(arbol))
		result = abb_nodo_agregar(arbol->raiz, clave, dato, arbol->comparar_clave, arbol->destruir_dato);
	else
		result = (arbol->raiz = abb_nodo_crear(clave,dato)) != NULL?AGREGADO:ERROR;

	if (result == AGREGADO)
		arbol->tamanio++;

	return result == ERROR?false:true;
}

void *abb_borrar(abb_t *arbol, const char *clave)
{
	if (!arbol || !clave)
		return NULL;

	if (abb_esta_vacio(arbol))
		return NULL;

	int resultado;
	void *dato;

	if (!arbol->comparar_clave(arbol->raiz->clave,clave))
		{
			abb_nodo_t *raiz = arbol->raiz;
			dato = raiz->dato;
			resultado = QUITADO;

			if (!raiz->derecho && !raiz->izquierdo)
				{
					abb_nodo_destruir(raiz);

					arbol->raiz = NULL;
				}
			else if (!raiz->derecho)
				{
					arbol->raiz = raiz->izquierdo;
					abb_nodo_destruir(raiz);
				}
			else if (!raiz->izquierdo)
				{
					arbol->raiz = raiz->derecho;
					abb_nodo_destruir(raiz);
				}
			else
				{
					abb_nodo_t *sucesor,*temp;

					int pendiente = abb_nodo_calcular_pendiente(raiz);

					if (pendiente > 0)
						{
							sucesor = abb_nodo_buscar_sucesor_derecho(raiz->izquierdo);
							sucesor->derecho = raiz->derecho;
							temp = sucesor;
							while (temp->izquierdo)
								temp = temp->izquierdo;
						}
					else
						{
							sucesor = abb_nodo_buscar_sucesor_izquierdo(raiz->derecho);
							sucesor->izquierdo = raiz->izquierdo;
							temp = sucesor;
							while (temp->derecho)
								temp = temp->derecho;
						}

					abb_nodo_t *padre = abb_nodo_buscar_padre(raiz,sucesor,arbol->comparar_clave);

					if (padre->derecho == sucesor)
						padre->derecho = NULL;
					else if (padre->izquierdo == sucesor)
						padre->izquierdo = NULL;

					if (pendiente > 0)
						temp->izquierdo = raiz->izquierdo;
					else
						temp->derecho = raiz->derecho;

					sucesor->altura = raiz->altura;

					abb_nodo_destruir(raiz);

					arbol->raiz = sucesor;
				}
		}
	else
		dato = abb_nodo_quitar(arbol->raiz,clave,arbol->comparar_clave,&resultado);

	if (resultado == QUITADO)
		arbol->tamanio--;
	
	return dato;
}

void *abb_obtener(const abb_t *arbol, const char *clave)
{
	if (!arbol)
		return NULL;

	return abb_nodo_obtener(arbol->raiz,clave,arbol->comparar_clave);
}

bool abb_pertenece(const abb_t *arbol, const char *clave)
{
	if (!arbol)
		return false;

	return abb_nodo_pertenece(arbol->raiz,clave,arbol->comparar_clave);
}

void abb_destruir(abb_t *arbol)
{
	if (!arbol)
		return;

	if (!abb_esta_vacio(arbol))
		abb_nodo_destruir_arbol(arbol->raiz,arbol->destruir_dato);

	free(arbol);
}

bool abb_nodo_iterar(const abb_nodo_t *nodo, bool (*visitar) (const char *, void *, void *), void *extra)
{
	if (!nodo)
		return true;

	if (abb_nodo_iterar(nodo->izquierdo,visitar,extra))
		if (visitar(nodo->clave,nodo->dato,extra))
			return abb_nodo_iterar(nodo->derecho,visitar,extra);
	return false;
}

void abb_in_order(abb_t *arbol,bool (*visitar)(const char *,void *,void *),void *extra)
{
	if (!arbol)
		return;
	
	if (!visitar)
		return;
	abb_nodo_iterar(arbol->raiz,visitar,extra);
}

void iter_pila_apilar (pila_t* iter_pila, abb_nodo_t* raiz)
{
	if (!raiz)
		return; 

	pila_apilar (iter_pila, raiz);
	iter_pila_apilar (iter_pila, raiz ->izquierdo);
}

abb_iter_t *abb_iter_in_crear(const abb_t *arbol)
{
	if (!arbol)
		return NULL;

	abb_iter_t *iter = malloc(sizeof(abb_iter_t));

	if (!iter)
		return NULL;

	iter->iter_pila = pila_crear ();
	if (!iter->iter_pila)
	{
		free (iter);
		return NULL;
	}
	
	iter_pila_apilar (iter->iter_pila, arbol->raiz);

	return iter;
}

bool abb_iter_in_al_final(const abb_iter_t *iter)
{
  if (!iter)
     return true;
  return pila_esta_vacia(iter->iter_pila);
}

bool abb_iter_in_avanzar(abb_iter_t *iter)
{
	if (!iter)
		return false;

	if (abb_iter_in_al_final(iter))
		return false;

	abb_nodo_t* abb_nodo = pila_desapilar (iter->iter_pila);
	iter_pila_apilar (iter->iter_pila, abb_nodo->derecho);
	return true;
}

const char *abb_iter_in_ver_actual(const abb_iter_t *iter)
{
	if (!iter)
		return NULL;

	if (abb_iter_in_al_final (iter))
		return NULL;

	abb_nodo_t* abb_nodo = pila_ver_tope (iter->iter_pila);
	if (!abb_nodo)
		return NULL;
		
	return abb_nodo->clave;
}

void abb_iter_in_destruir(abb_iter_t* iter)
{
	if (!iter)
		return;

	pila_destruir (iter->iter_pila);
	free(iter);
}
